package Dynamic_programming;

import com.sun.org.apache.xpath.internal.operations.Mod;
import org.junit.Test;

import java.io.*;
import java.util.*;

/**
 * @author 29349
 */
public class Test012 {
    public int[][] updateMatrix(int[][] mat) {
        int []dx=new int[]{-1,0,1,0};
        int[] dy=new int[]{0,1,0,-1};
        int m=mat.length;int n=mat[0].length;
        Queue<int[]> queue=new LinkedList<>();
        boolean[][] flag=new boolean[m][n];
        int[][] dp=new int[m][n];
        for (int i = 0; i <m ; i++) {
            for (int j = 0; j <n ; j++) {
               if(mat[i][j]==0){
                   flag[i][j]=true;
                   queue.offer(new int[]{i,j});
               }
            }
        }
        while (!queue.isEmpty()){
        int []ints=queue.poll();
        int l=ints[0];
        int lm=ints[1];
            for (int i = 0; i <4 ; i++) {
                int x=l+dx[i],y=lm+dy[i];
                if(x>=0&&x<m&&y>=0&&y<n&&!flag[l][lm]){
                    dp[x][y]=dp[l][lm]+1;
                    flag[x][y]=true;
                    queue.offer(new int[]{x,y});
                }
            }
        }
        return dp;
    }
    public int getMaxLen(int[] nums) {
        int positive = nums[0] > 0 ? 1 : 0;
        int negative = nums[0] < 0 ? 1 : 0;
        int max = positive;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                positive++;
                negative = negative > 0 ? negative + 1 : 0;
            } else if (nums[i] < 0) {
                int newNegative = positive + 1;
                int newPositive = negative > 0 ? negative + 1 : 0;
                negative = newNegative;
                positive = newPositive;
            } else {
                positive = 0;
                negative = 0;
            }
            max = Math.max(max, positive);
        }
        return max;
    }
    public int maxScoreSightseeingPair(int[] values) {
      int  dp= values[0];int ll=0;
        for (int i = 1; i <values.length ; i++) {
            dp=Math.max(dp,ll+values[i]-i);
            ll=Math.max(ll,values[i]+i);
        }
        return ll;
    }

    public int maxProfit(int[] prices) {
        int min=Integer.MAX_VALUE;int max=0;
        for (int i = 0; i <prices.length ; i++) {
            if(prices[i]<min){
                min=prices[i];
            }else if(prices[i]-min>max){
                max=prices[i]-min;
            }
        }
        return max;
    }
    public int maxProfit1(int[] prices) {
    int sum=0;int min=Integer.MAX_VALUE;int max=0;
        for (int i = 1; i <prices.length ; i++) {
            if(prices[i]<prices[i-1]){
                min=prices[i];
                sum+=max;
            }else {
                if(prices[i]<min){
                    min=prices[i];
                }else if(prices[i]-min>0){
                    max=prices[i]-min;
                }
            }
        }
        return sum;
    }
    public int translateNum(int num) {
        String s= String.valueOf(num);
        int[]dp=new int[s.length()];
            dp[0] = 1;
        for (int i = 1; i <s.length() ; i++) {
            int x=s.charAt(i)-'0';
            if(x>0&&x<10){
                dp[i]+=dp[i-1]+1;
            }
            int y=s.charAt(i-1)-'0';
            if(y*10+x>9&&y*10+x<26){
                dp[i]++;
            }
        }
return dp[s.length()-1];
    }
    public int lengthOfLongestSubstring(String s) {
        if(s==null||s.length()==0){
            return 0;
        }
        Map<Character,Integer> map=new HashMap<>();
        int l=0,r=1,max=1;
        map.put(s.charAt(0),0);
        while (r<s.length()){
            if(map.containsKey(s.charAt(r))){
                max=Math.max(max,r-l);
                l=map.get(s.charAt(r))+1;
                map.put(s.charAt(r),r);
                System.out.println(s.charAt(l)+"  "+s.charAt(r));
            }
            map.put(s.charAt(r),r);
            r++;

            System.out.println();
        }
        return max;
    }
    public int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int n=nums.length;
        int min=0;
        for (int i = 0; i < n; i++) {
           if(nums[i]>0){
               min=i;
               System.out.println(i);
               break;
           }
        }
        int res=n+1;
        for (int i = min; i <=n ; i++) {
            if(nums[i]!=i-min+1){
                return i-min+1;
            }
        }
        return n+1;
    }

    final int MOD=1337;
    public int superPow(int a, int[] b) {
    if(a>MOD){
        a%=MOD;
    }
    double sum=1;
        int length=b.length;long lp=1;
        for (int i = length-1; i >=0; i--) {
            long index=lp*b[i];
            if(b[i]!=0){
                sum*=sumAdd(a,index);
            }
                lp*=10;
        }
        return (int) (sum%MOD);
    }
    public int sumAdd(int a,long index){
        if(index==0){
            return 1;
        }
        int y=sumAdd(a,index/2)% MOD;
    return index%2==0 ?( y*y)%MOD:(y*y*a)%MOD;
    }
    public int myPow(int x, int n) {
   return n>=0? sumAdd1(x,n):1/sumAdd1(x,-n);
    }
    public int sumAdd1(int a,long index){
       int res=1;
       int a_temp=a;
       while (index>0){
           if(index%2==1){
               res*=a_temp;
           }
           a_temp*=a_temp;
           index/=2;
       }
       return res;
    }
    public String truncateSentence(String s, int k) {
    if(s==null||s.length()==0){
        return s;
    }
    int index=0;
        for (int i = 0; i <s.length(); i++) {
            char c=s.charAt(i);
            if(c==' '){
                index++;
                if(index==k){
                    return s.substring(0,i-1);
                }
            }
        }
        return s;
    }

    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public List<List<Integer>> combine(int n, int k) {
        add(1,n,k);
        return ans;
    }
    public void add(int cur,int n,int k){
        if(temp.size()+n-cur+1<k){
            return;
        }
        if(temp.size()==k){
            ans.add(new ArrayList<>(temp));
        }
        temp.add(cur);
        add(cur+1,n,k);
        temp.remove(temp.size()-1);
        add(cur+1,n,k);
    }
    public List<List<Integer>> combine1(int n, int k) {
        List<Integer> temp = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 初始化
        // 将 temp 中 [0, k - 1] 每个位置 i 设置为 i + 1，即 [0, k - 1] 存 [1, k]
        // 末尾加一位 n + 1 作为哨兵
        for (int i = 1; i <= k; ++i) {
            temp.add(i);
        }
        temp.add(n + 1);

        int j = 0;
        while (j < k) {
            ans.add(new ArrayList<Integer>(temp.subList(0, k)));
            j = 0;
            // 寻找第一个 temp[j] + 1 != temp[j + 1] 的位置 t
            // 我们需要把 [0, t - 1] 区间内的每个位置重置成 [1, t]
            while (j < k && temp.get(j) + 1 == temp.get(j + 1)) {
                temp.set(j, j + 1);
                ++j;
            }
            // j 是第一个 temp[j] + 1 != temp[j + 1] 的位置
            temp.set(j, temp.get(j) + 1);
        }
        return ans;
    }
    public List<List<Integer>> permute(int[] nums) {
        boolean [] flag=new boolean[nums.length];
    addNum(nums,flag);
    return ans;
    }
    public void addNum(int[] nums,boolean[] flag){
        if(temp.size()==nums.length){
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i <nums.length ; i++) {
            if(!flag[i]) {
                flag[i]=true;
                temp.add(nums[i]);
                addNum(nums, flag);
                temp.remove(temp.size() - 1);
                flag[i]=false;
            }
        }
    }
    public List<List<Integer>> permute1(int[] nums) {
        List<List<Integer>> ans=new ArrayList<>();
        List<Integer> temp=new ArrayList<>();
        for (int y:nums) {
            temp.add(y);
        }
        swapAdd(ans,temp,0);
        return ans;
    }
    public void swapAdd(List<List<Integer>> ans,List<Integer> temp,int index){
        if(index==temp.size()){
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i <temp.size() ; i++) {
            Collections.swap(temp,index,i);
            swapAdd(ans,temp,index+1);
            Collections.swap(temp,i,index);
        }
    }

    public List<String> letterCasePermutation(String s) {
        List<StringBuilder> ans = new ArrayList();
        ans.add(new StringBuilder());
        for (char c: s.toCharArray()) {
            int n = ans.size();
            if (Character.isLetter(c)) {
                for (int i = 0; i < n; ++i) {
                    ans.add(new StringBuilder(ans.get(i)));
                    ans.get(i).append(Character.toLowerCase(c));
                    ans.get(n+i).append(Character.toUpperCase(c));
                }
            } else {
                for (int i = 0; i < n; ++i) {
                    ans.get(i).append(c);
                }
            }
        }

        List<String> finalans = new ArrayList();
        for (StringBuilder sb: ans) {
            finalans.add(sb.toString());
        }
        return finalans;
    }
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        int[] xl=new int[]{1,0,-1,0};
        int[] yl=new int[]{0,1,0,-1};
    Queue<int[]> queue=new LinkedList<>();
    if(grid[row][col]==color){
        return grid;
    }
    boolean flag=false;
    if(row==0||col==0||row==grid.length-1||col==grid[0].length-1){ flag=true;}
    int oldColor=grid[row][col];
    queue.add(new int[]{row,col});
    while (!queue.isEmpty()){
        int[] temp=queue.poll();
        int x=temp[0];
        int y=temp[1];
        for (int i = 0; i < 4; i++) {
            int lx=x+xl[i];
            int ly=y+yl[i];
            if(lx==row&&ly==col){
                continue;
            }
            if(lx>=0&&lx<grid.length&&ly>=0&&ly<grid[0].length&&grid[lx][ly]==oldColor){
                queue.offer(new int[]{lx,ly});
                grid[lx][ly]=color;
            }
        }
    }
    if(flag){
        grid[row][col]=color;
    }
    return grid;
    }
    public String addBinary(String a, String b) {
       int a1=Integer.valueOf(a,2);
       int a2=Integer.valueOf(b,2);
       int res=a1+a2;
       return Integer.toString(res,2);
    }
    public int mySqrt(int x) {
    if(x==0){
        return 1;
    }
    int x1=x,c=x;
        while (true) {
            x1= (int) (0.5*(x-c/x));
            if(x1<=x){
                break;
            }
        }
        return x1;
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }
        if(p==null||q==null||p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    @Test
    public void xx() {
//        // System.out.println(maxProfit(new int[]{7, 2, 4, 1, 5}));
//        // System.out.println(lengthOfLongestSubstring("pwwkew"));
////        System.out.println(superPow(2147483647,new int[]{2,0,0}));
//        System.out.println(letterCasePermutation("a1b2"));
        //  int[][] ints = colorBorder(new int[][]{{1, 2, 1, 2, 1, 2}, {2, 2, 2, 2, 1, 2}, {1, 2, 2, 2, 1, 2}}, 1, 3, 1);
      //  System.out.println(sortedArrayToBST(new int[]{-10, -3, 0, 5, 9}));
        //System.out.println(shortestCompletingWord("1s3 PSt", new String[]{"step", "steps", "stripe", "stepple"}));
        System.out.println(isPalindrome("0P"));
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        int mid=nums.length/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=sortedArrayToBST(nums,0,mid-1);
        root.right=sortedArrayToBST(nums,mid+1,nums.length-1);
        return root;
    }
    public TreeNode sortedArrayToBST(int[] nums,int l,int r) {
        if(l>=r){
            return null;
        }
        int mid=(r-l)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=sortedArrayToBST(nums,l,mid-1);
        root.right=sortedArrayToBST(nums,mid+1,r);
        return root;
    }
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left,TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
    public String shortestCompletingWord(String licensePlate, String[] words) {
        Map<Character,Integer> map=new HashMap<>();
        for (int i = 0; i <licensePlate.length() ; i++) {
            char c=licensePlate.charAt(i);
            if(c>'a'&&c<'z'||c>'A'&&c<'Z'){
                map.put(Character.toLowerCase(c),map.getOrDefault(Character.toLowerCase(c),0)+1);
            }
        }
        for (int i = 0; i <words.length ; i++) {
            String s=words[i];
            for (int j = 0; j <s.length() ; j++) {
                char c=s.charAt(i);
                if(c>'a'&&c<'z'||c>'A'&&c<'Z'){
                    char c1=Character.toLowerCase(c);
                   if(map.containsKey(c1)){
                       map.put(c1,map.get(c1)-1);
                   }
                }
            }
            int x=0;
            for (Map.Entry<Character, Integer> entry:map.entrySet()) {
                    x+=entry.getValue();
            }
            if(x<=0){
                return s;
            }
        }
        return new String();
    }
    public int minDepth(TreeNode root) {
    if(root==null){
        return 0;
    }
    return Math.min(minDepth(root.left),minDepth(root.right))+1;
    }
    public boolean isPalindrome(String s) {
        if(s==null){
            return true;
        }
        StringBuilder stringBuilder=new StringBuilder();
        for (int i = 0; i <s.length() ; i++) {
            char c=s.charAt(i);
            if(Character.isLetter(c)||Character.isDigit(c)){
                stringBuilder.append(Character.toLowerCase(c));
            }
        }
        String s1=stringBuilder.toString();
        int l=0;int r=s1.length()-1;
        while (l<r){
            if(s1.charAt(l)!=s1.charAt(r)){
                return false;
            }
            l++;r--;
        }
        return true;
    }

    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int[] X = new int[grid.length] ;
        int[] Y = new int[grid[0].length] ;
        for (int i = 0; i < grid.length ; i++) {
            int x = Integer.MIN_VALUE ;
            int y = Integer.MIN_VALUE ;
            for (int j = 0; j <grid[0].length ; j++) {
                if(x <grid[i][j]){
                    x = grid[i][j] ;
                }
                if(y < grid[j][i]){
                    y = grid[j][i];
                }
            }
            X[i] = x;
            Y[i] = y;
        }
        int sum=0;
        for (int i = 0; i < grid.length ; i++) {
            for (int j = 0; j < grid[0].length ; j++) {
                int temp=Math.min(X[i],Y[j]);
                sum+=temp-grid[i][j];
                grid[i][j]=temp;
            }
        }
        return sum;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       /* while (headA!=null){
            ListNode pre=headB;
           while (pre!=null){
               if(headA==pre){
                   return headA;
               }
               pre=pre.next;
           }
           headA=headA.next;
        }
        return null;*/
        Set<ListNode> set=new HashSet<>();
        while (headA!=null){
            set.add(headA);
            headA=headA.next;
        }
        while (headB!=null){
            if(set.contains(headB)){
                return headB;
            }
            headB=headB.next;
        }
        return null;
    }
    @Test
    public void xx1() {
  /*  System.out.println(maxIncreaseKeepingSkyline(new int[][]{
            {3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3}, {0, 3, 1, 0}
    }));*/
        System.out.println(convertToTitle(701));
    }
    public String convertToTitle(int columnNumber) {
        char[] chars=new char[]{'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
        StringBuilder stringBuilder=new StringBuilder();
        while (columnNumber>1){
            int x=(columnNumber%26)-1;
            if(x<0){
                x=25;
            }
            stringBuilder.append(chars[x]);
            columnNumber=(columnNumber-columnNumber%26)/26;
        }
        return stringBuilder.reverse().toString();
    }
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < nums.length ; i++) {
        }
        return -1;
    }
    public int titleToNumber(String columnTitle) {
        if(columnTitle == null || columnTitle.length() == 0){
            return 0;
        }
        int sum=0;
        for (int i = 0; i < columnTitle.length(); i++) {
            char c = columnTitle.charAt(i);
            sum*=26;
            sum+=c-'A';
        }
        return sum;
    }
    public boolean isHappy(int n) {
        Set<Integer> set=new HashSet<>();
        while (n!=1&&!set.contains(n)){
           int sum=0;
            while (n>0){
                int d=n%10;
                n=n/10;
                sum+=d*d;
            }
            n=sum;
        }
        return n==1;
    }
    public boolean isIsomorphic(String s, String t) {
    Map<Character,Character> map=new HashMap<>();
   if(s==null&&t==null){
       return true;
   }
   if(s==null||t==null||s.length()!=t.length()){
       return false;
   }
        for (int i = 0; i <s.length() ; i++) {
            char c=s.charAt(i);
            if(map.containsKey(c)){
                c=map.get(c);
                if(c!=t.charAt(i)){
                    return false;
                }
            }else {
                map.put(c,t.charAt(i));
            }
        }
        return true;
    }
    public int maxProfit2(int[] prices) {
        if(prices==null||prices.length==0){
            return 0;
        }
        int []dp = new int[prices.length];
        dp[0]=prices[0];
        dp[1] = prices[1]-prices[0];
        for (int i = 2; i < prices.length ; i++) {
            dp[i] = Math.max(prices[i]-dp[i-1],prices[i]-dp[i-2]);
        }
        return Math.max(dp[dp.length-1],dp[dp.length-2]);
    }
    @Test
    public void test1() throws IOException {
        final String BASE_CONFIG="/data/new/config";
        final String SUFFIX=".properties";
        InputStream in = new BufferedInputStream(new FileInputStream(new File(BASE_CONFIG,"sobot-"+"ZN"+SUFFIX)));
        Properties properties = new Properties();
        properties.load(new InputStreamReader(in,"utf-8"));
        properties.list(System.out);
        System.out.println("==============================================");
        String property = properties.getProperty("ws.export."+"Priority(required)");
        System.out.println("property = " + property);
       // System.out.println(summaryRanges(new int[]{0, 1, 2, 4, 5, 7}));
       /* System.out.println(addDigits(10));*/
    }

    public List<String> summaryRanges(int[] nums) {
        List<String> strings=new ArrayList<>();
        int i=0;
        i++;
        while (i<nums.length){
            int low=i;
            while (i<nums.length&&nums[i+1]==nums[i]){
                i++;
            }
            int high=i-1;
            StringBuilder stringBuilder=new StringBuilder(nums[low]);
            if(high>low){
                stringBuilder.append("->");
                stringBuilder.append(nums[high-1]);
            }
            strings.add(stringBuilder.toString());
        }
        return strings;
    }
    public boolean isPalindrome(ListNode head) {
       ListNode pre=head;
       ListNode next=pre.next;
       while (pre.next!=null&&next.next!=null){
           pre=pre.next;
           next=next.next.next;
       }
       ListNode listNode=null;
       while (pre!=null){
           ListNode p=pre.next;
           pre.next=listNode;
           listNode=pre;
           pre=p;
       }
       while (listNode!=null){
           if(listNode.val!=head.val){
               return false;
           }
       }
       return true;
    }
    public List<String> binaryTreePaths(TreeNode root) {
    List<String> list=new ArrayList<>();
    find(list,"",root);
    return list;
    }
    public void find(List<String> list,String path,TreeNode root){
        if(root!=null) {
            StringBuilder stringBuilder=new StringBuilder(path);

            stringBuilder.append(Integer.toString(root.val));
            if(root.left==null&&root.right==null){
                list.add(stringBuilder.toString());
            }else {
                stringBuilder.append("->");
                find(list,stringBuilder.toString(),root.left);
                find(list,stringBuilder.toString(),root.right);

            }
        }
    }
    public int addDigits(int num) {
        while (num>=10){
            int sum=0;
            while (num>0){
                sum+=num%10;
                num=num/10;
            }
            num=sum;
        }
        return num;
    }
    public int numWaterBottles(int numBottles, int numExchange) {
        int sum=0;
        if(numBottles<numExchange){
            return numBottles;
        }
        while (numBottles/numExchange>0){
            sum+=numBottles-numBottles%numExchange;
            int change=(numBottles/numExchange+numBottles%numExchange);
            numBottles=change;
        }
      return numBottles==0? sum:(sum+numBottles);
    }
    public char findTheDifference(String s, String t) {
       /* Map<Character,Integer> map=new HashMap<>();
            for (int i = 0; i <t.length() ; i++) {
                if (i<s.length()){
                    map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
                }
                map.put(t.charAt(i),map.getOrDefault(t.charAt(i),0)-1);
            }
            for (int i = 0; i <t.length() ; i++) {
               int n= map.getOrDefault(t.charAt(i),-1);
               if(n<0) {
                   return t.charAt(i);
               }
            }
            return ' ';*/
        char sum=t.charAt(0);
        for (int i = 0; i <t.length() ; i++) {
           sum= (char) (sum^t.charAt(i+1)^s.charAt(i));
        }
        return  sum;
    }
    public boolean isSubsequence(String s, String t) {
        if(s==null||s.length()==0){
            return true;
        }
        int index=0;
        for (int i = 0; i <t.length() ; i++) {
            if(t.charAt(i)==s.charAt(index)){
                index++;
                if (index==s.length()){
                    break;
                }
            }
        }
        return index==s.length();
    }
    int sum =0;
    public int sumOfLeftLeaves(TreeNode root) {
        return sum;
    }
    public void  add(TreeNode root){
        if(root==null){
            return;
        }
        if(root.left!=null&&root.left.left==null&&root.right==null){
            sum+=root.left.val;
        }
        add(root.left);
        add(root.right);
    }
    public int longestPalindrome(String s) {
        Map<Character,Integer> map=new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
        }
        int sum=0;
        for (Map.Entry<Character,Integer> e:map.entrySet()) {
            int x=e.getValue();
            if(x>=2){
                sum+=(x/2);
            }
        }
        return sum<s.length() ? sum+1:sum;
    }
    public List<String> fizzBuzz(int n) {
        String s1="Fizz";
        String s2="Buzz";
        List<String> list=new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if(i%3==0&&i%5==0){
                list.add(s1+s2);
            }else if(i%3==0){
                list.add(s1);
            }else if(i%5==0){
                list.add(s2);
            }else {
                list.add(String.valueOf(i));
            }
        }
        return list;
    }
    public int thirdMax(int[] nums) {
      /*  Arrays.sort(nums);
        if(nums.length<3){
            return nums[0];
        }
        int x=1,pre=nums[nums.length-1],index=0;
        for (int i = nums.length-1; i>=0 ; i--) {
            index=i;
            if(pre!=nums[i]){
                x++;
                if(x==3){
                    break;
                }
            }
        }
        return x==3 ? nums[index] : nums[0];*/
        Integer a=null,b=null,c=null;
        for (int num : nums) {
          if(a==null||num>a){
              c=b;
              b=a;
              a=num;
          }else if(b==null||num>b){
              c=b;
              b=num;
          }else if(b!=null&&(c==null||num>c)){
              c=num;
          }
        }
        return c == null ? a : c;
    }
    @Test
    public void xx11() {
        System.out.println(addStrings("1", "9"));

    }
    public String addStrings(String num1, String num2) {
        if(num1 == null || num2 == null){
            return num1 == null ? num2 : num1;
        }
        StringBuilder stringBuilder = new StringBuilder();
        int l = num1.length() - 1,r = num2.length() - 1,add = 0;
        while (l >=0 || r >=0){
            int a = l < 0 ? 0: num1.charAt(l) - '0';
            int b = r < 0 ? 0: num2.charAt(r) - '0';
            int x = a + b + add;
            if(x>=10){
                add = x /10;
                x %= 10;
            }else {
                add = 0;
            }
            stringBuilder.append(String.valueOf(x));
            l--;
            r--;
        }
        if(add != 0){
            stringBuilder.append(add);
        }
        return stringBuilder.reverse().toString();
    }
    public int countSegments(String s) {
       /* int sum=0;
        char c1 = ' ';
        for (int i = 0; i < s.length();i++) {
            char c = s.charAt(i);
            if(!Character.isLetter(c) && Character.isLetter(c1)){
                sum++;
            }
            c1 = c;
        }
        return Character.isLetter(s.charAt(s.length()-1)) ? sum + 1 : sum;*/
        String [] strings=s.split(" ");
        int sum = 0;
        for (String x: strings
             ) {
            if(x!=null&&x.length()>0){
                sum++;
            }
        }
        return  sum;
    }
    public int arrangeCoins(int n) {
        int sum = 0;
        int x = 1;
        while (n > x){
            n -= x;
            x++;
            sum++;
        }
        return sum;
    }
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int[] ints=new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ints[nums[i]]++;
        }
        List<Integer> list=new ArrayList<>();
        for (int i = 0; i < ints.length; i++) {
            if(ints[i] == 0){
                list.add(i+1);
            }
        }
        return list;
    }
    public int findContentChildren(int[] g, int[] s) {
        int l=0;
        int r=0;
        Arrays.sort(g);
        Arrays.sort(s);
        int sum=0;
        while (l<g.length&&r<s.length){
            if(g[l] <= s[r]){
                l++;
                r++;
                sum++;
            }else {
                r++;
            }
        }
        return sum;
    }
    public boolean repeatedSubstringPattern(String s) {
        if(s==null || s.length() == 0){
            return true;
        }
        StringBuilder stringBuilder = new StringBuilder();
        char c = s.charAt(0);
        stringBuilder.append(c);
        for (int i = 1; i < s.length(); i++) {
            char a = s.charAt(i);
            if(a == c){
                break;
            }
            stringBuilder.append(a);
        }
        if(stringBuilder.length() == s.length()){
            return true;
        }
        String s1 = stringBuilder.toString();
        while (s.contains(s1)){
            s=s.replace(s1,"");
        }
        return s.length() == 0;
    }
    public int[] searchRange(int[] nums, int target) {
        int[] res=new int[2];
        res[0] = -1;
        res[1] = -1;
        int l = 0,r = nums.length-1;
        while (l<r){
            if(nums[l] == target && nums[r] == target){
                break;
            } else  if(nums[l] == target){
                res[0] =l;
                r--;
            }else if(nums[r] == target){
                res[1] = r;
              l++;
            }else {
                l++;
                r--;
            }
        }
        if(l==r&&nums[l]==target){
            res[0]=l;
            res[1]=l;
        }
        return res;
    }
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int res=0;
        for (int i = 0; i < houses.length; i++) {
            int ta = Integer.MAX_VALUE;
            for (int j = 0; j < heaters.length; j++) {
                ta = Math.min(ta,Math.abs(houses[i] - heaters[j]));
            }
            res = Math.max(res,ta);
        }
        return res;
      /*  Arrays.sort(houses);
        Arrays.sort(heaters);
        int[] min =new int[heaters.length+1];
        int x = heaters[0] - houses[0];
        min[0] = x>0 ? x: -x;
        for (int i = 1; i < heaters.length; i++) {
           int temp =  (heaters[i] + heaters[i-1])/2 - heaters[i];
           int t =(heaters[i] + heaters[i-1])/2 - heaters[i-1];

        }
        int y = houses[houses.length-1] - heaters[heaters.length-1];
        min[heaters.length] = y>0 ? y:-y;
        int r = 0;
        for (int i = 0; i < min.length; i++) {
            r = Math.max(r,min[i]);
        }
return  r;*/
    }
    public String[] findWords(String[] words) {
        String s="12210111011122000010020202";
        StringBuilder stringBuilder=new StringBuilder();
        boolean flag = true;
        for (int i = 0; i < words.length; i++) {
            String temp  = words[i];
            int l = s.charAt(Character.toLowerCase(temp.charAt(0)) - 'a');
            boolean flag1 = true;
            for (int j = 1; j < s.length(); j++) {
                if(l != s.charAt(Character.toLowerCase(temp.charAt(j)) - 'a')){
                    flag1 =false;
                    break;
                }
            }
            if(flag1){
                if (!flag){
                    stringBuilder.append('-');
                }
                stringBuilder.append(temp);
                flag = false;
            }
        }
        return stringBuilder.toString().split("-");
    }
    List<Integer> list=new ArrayList<>();
    int base,count,maxcount;
    public int[] findMode(TreeNode root) {
    dfs(root);
    int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void dfs(TreeNode root) {
        if(root==null){
            return;
        }
        dfs(root.left);
        update(root.val);
        dfs(root.right);
    }

    private void update(int x) {
        if(x==base){
            count++;
        }else {
            base = x;
            count = 1;
        }
        if(count == maxcount){
            list.add(x);
        }else  if(count>maxcount){
            maxcount = count;
            list.clear();
            list.add(x);
        }
    }
    public String convertToBase7(int num) {
        StringBuilder stringBuilder=new StringBuilder();
      boolean flag = true;
      if(num<0){
          flag =false;
      }
      int add=0;
      while (num>0){
          stringBuilder.append(String.valueOf(num%7+add));
          if(num%7==0){
              add = 1;
          }else {
              add = 0;
          }

          num=num/7;
      }
      if(!flag){
          stringBuilder.append("-");
      }
      return stringBuilder.reverse().toString();
    }
    public boolean checkPerfectNumber(int num) {
    sum =1;
    int index =2;
    while (index != num){
        if(num%index==0){
            sum+=index;
        }
        index++;
    }
    return sum == num;
    }
    public int dayOfYear(String date) {
    String[] day = date.split("-");
    int[] months = new int[]{31,28,31,30,31,30,31,31,30,31,30,31};
    if(leapYear(day[0])){
        months[1] = 29;
    }
    int sum = 0;
        for (int i = 0; i < Integer.parseInt(day[1])-2; i++) {
            sum += months[i];
        }
        sum += Integer.parseInt(day[2]);
        return sum;

    }
    private boolean leapYear(String s) {
        Integer  year = Integer.parseInt(s);
        if((year%4==0 && year%100 != 0)||year%400 == 0){
            return true;
        }
        return false;
    }
    public String reverseStr(String s, int k) {
        char[] chars=s.toCharArray();
        for (int i = 0; i < s.length(); i+=2*k) {
            change(chars,i,Math.min(i+k,s.length())-1);
        }
        return String.valueOf(chars);
    }

    private void change(char[] chars, int min, int k) {
        while (min<k){
            char temp = chars[min];
            chars[min] = chars[k];
            chars[k] = temp;
        }
    }
    int ss = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        ss = 1;
        find(root);
        return ss - 1;
    }

    private int find(TreeNode root) {
        if(root == null){
            return 0;
        }
        int l = find(root.left);
        int r = find(root.right);
        ss = Math.max(l,r)+ss;
        return ss+1;
    }
    public boolean checkRecord(String s) {
            if(s.contains("LLL")){
                return false;
            }
           int sum = 0;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if(c == 'A'){
                    sum++;
                    if(sum==2){
                        return false;
                    }
                }
            }
            return true;
    }
    public int maxDepth(Node1 root) {
        if(root==null){
            return 0;
        }
        int sum = 0;
        for (Node1 node: root.children) {
            sum = Math.max(sum,maxDepth(node));
        }
        return sum+1;
    }
    public int arrayPairSum(int[] nums) {
    Arrays.sort(nums);
    int sum = 0;
        for (int i = 0; i < nums.length; i+=2) {
            sum+=nums[i];
        }
        return sum;
    }
    public int findTilt(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        int sum = 0;
        for (int s: list
             ) {
            sum += s;
        }
return sum;
    }
    public  int   find(List<Integer> list,TreeNode root){
        if(root==null){
            return 0;
        }
        int l=0,r=0;


        l= find(list,root.left);

            r = find(list,root.right);

        int x=Math.abs(l-r);
        list.add(x);
        return l+r+root.val;
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null){
            return false;
        }
        return isSon(root,subRoot)||isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot);
    }

    private boolean isSon(TreeNode pre, TreeNode subRoot) {
        if(subRoot==null){
            return true;
        }
        if(pre==null){
            return false;
        }
        return isSon(pre.left,subRoot.left)&&isSon(pre.right,subRoot.right);
    }
    public List<Integer> preorder(Node1 root) {
      /*  List<Integer> list=new ArrayList<>();
        fingSon(list,root);
        return list;*/
        List<Integer> list=new ArrayList<>();
        Stack<Node1> s=new Stack<>();
        if(root==null){
            return list;
        }
        s.push(root);
        while (!s.isEmpty()){
            Node1 node1=s.pop();
            list.add(node1.val);
            List<Node1> children = node1.children;

            for (int i = children.size()-1; i >=0 ; i--) {
                    if(children.get(i)!=null){
                       s.push(children.get(i));
                    }
                }

        }
        return list;
    }
    private void fingSon(List<Integer> list, Node1 root) {
        if(root == null){
            return;
        }
        list.add(root.val);
        List<Node1> children = root.children;
        for (Node1 n :children) {
            fingSon(list,n);
        }
    }
    public List<Integer> postorder(Node1 root) {
   /* List<Integer> list =new ArrayList<>();
    postorder(list,root);
    return list;*/
        List<Integer> list =new ArrayList<>();
        Stack<Node1> s=new Stack<>();
        if(root==null){
            return list;
        }
        s.push(root);
        while (!s.isEmpty()){
            Node1 node1=s.pop();
            List<Node1> children = node1.children;
            for (int i = children.size(); i >=0 ; i--) {
                s.push(children.get(i));
            }
            list.add(node1.val);
        }
        return list;
    }

    private void postorder(List<Integer> list, Node1 root) {
        if (root==null){
            return;
        }
        List<Node1> children = root.children;
        for (Node1 n:children
             ) {
            postorder(list,n);
        }
        list.add(root.val);
    }
    public int findLHS(int[] nums) {
    Arrays.sort(nums);
    int l=0,r=0;
    int sum=-1;
       while (r<nums.length){
           if(nums[r]-nums[l]<=1){
               sum=Math.max(sum,r-l+1);
               r++;
           } else if(nums[r]-nums[l]>1&&l<r){
               l++;
           }else {
              r++;
           }

       }
       return sum;
    }
    public String[] findRestaurant(String[] list1, String[] list2) {
    Map<String,Integer> map = new HashMap<>();
        for (int i = 0; i <list1.length ; i++) {
            map.put(list1[i],i);
        }
        List<String> strings=new ArrayList<>();
        int sum=Integer.MIN_VALUE;
        for (int i = 0; i < list2.length; i++) {
            if(map.containsKey(list2[i])){
                if(sum<(map.get(list2[i])+i)){
                    sum=map.get(list2[i])+i;
                    strings.clear();
                    strings.add(list2[i]);
                }else if(sum==(map.get(list2[i])+i)){
                    strings.add(list2[i]);
                }
            }
        }
        return strings.toArray(new String[]{});
    }
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
    int sum = 0;
        for (int i = 0; i < flowerbed.length; i++) {
            if(i == 0&&flowerbed[i] == 0&&flowerbed[i+1] == 0){
                sum++;
                flowerbed[i] = 1;
            } else   if(i == flowerbed.length-1&&flowerbed[i] == 0&& flowerbed[i-1] == 0){
                sum++;
                flowerbed[i] = 1;
            }else if(i>=0&&i<flowerbed.length-1&&flowerbed[i-1] ==0&& flowerbed[i] ==0&& flowerbed[i+1]==0){
                    sum++;
                    flowerbed[i] = 1;
                }
        }
        return sum == n;
    }
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder=new StringBuilder();
        dfs(stringBuilder,root);
        return stringBuilder.toString().replace("()" ,"");
    }

    private void dfs(StringBuilder stringBuilder, TreeNode root) {
        if (root==null){
            return;
        }
        stringBuilder.append(root.val);
        dfs(stringBuilder.append("("),root.left);
        stringBuilder.append(")");
        dfs(stringBuilder.append("("),root.right);
        stringBuilder.append(")");
    }
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        if(nums.length==3){
            return nums[0]*nums[1]*nums[2];
        }
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]<0){
                index++;
            }
        }
        if (index>=2&&index<nums.length-1){
            return nums[0]*nums[1] > nums[nums.length-1]*nums[nums.length-2] ?
                    nums[0]*nums[1]*nums[nums.length-1]:nums[nums.length-1]*nums[nums.length-2]*nums[0];
        }else if(index<2){
            return nums[nums.length-1]*nums[nums.length-2]*nums[nums.length-3];
        }else {
            return nums[0]*nums[1]*nums[2];
        }
    }
    public List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> treeNodes=new LinkedList<>();
        List<Double> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        treeNodes.add(root);
        while (!treeNodes.isEmpty()){
            int size = treeNodes.size();
            double sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode temp = treeNodes.poll();
                sum+=temp.val;
                if(temp.left!=null){
                    treeNodes.add(temp.left);
                }
                if(temp.right!=null){
                    treeNodes.add(temp.right);
                }
            }
            list.add(sum);
        }
        return list;
    }
    @Test
    public void xx2() {
        System.out.println(Double.MIN_VALUE<0);
       // System.out.println(findMaxAverage(new int[]{1, 12, -5, -6, 50, 3}, 4));

    }
    public double findMaxAverage(int[] nums, int k) {
        double sum = 0;
        double max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if(i<k){
                sum+=nums[i];
            }else {
                sum = sum + nums[i] - nums[i-k];
                max = Math.max(-1,max);
            }
        }
        return max/k;
    }
}
class Node1 {
    public int val;
    public List<Node1> children;

    public Node1() {}

    public Node1(int _val) {
        val = _val;
    }

    public Node1(int _val, List<Node1> _children) {
        val = _val;
        children = _children;
    }
}